package com.chj.chuji.tijie01;

public class CircularWords {
	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
//		int n = sc.nextInt();
		int n = 5;
		int[] vis = new int[n];
		String[] str = new String[] { "picture", "turepic", "icturep", "word", "ordw" };
		int cnt = 1;
//		for (int i = 0; i < n; i++) {
//			str[i] = sc.next();
//		}
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (vis[i] == 0 && str[i].length() == str[j].length()) {
					if (cmp(str[i], str[j])) {
						vis[i] = 1;
						vis[j] = 1;
						break;
					}
				}
			}
			if (vis[i] == 0) {
				cnt++;
			}
		}
		System.out.println(cnt);

		int n2 = 5;
		int[] vis2 = new int[n];
		String[] str2 = new String[] { "picture", "turepic", "icturep", "word", "ordw" };
		int cnt2 = 1;
		for (int i = 1; i < n2; i++) {
			for (int j = 0; j < i; j++) {
				if (vis2[i] == 0 && str2[i].length() == str2[j].length()) {
					if (isRotation(str[i], str[j])) {
						vis2[i] = 1;
						vis2[j] = 1;
						break;
					}
				}
			}
			if (vis2[i] == 0) {
				cnt2++;
			}
		}
		System.out.println(cnt2);
	}

	private static boolean cmp(String s, String s1) {
		char[] str1 = s.toCharArray();
		char[] str2 = s1.toCharArray();
		int len = s.length();
		for (int i = 0; i < len; i++)/// 每次移动多少
		{
			boolean flag = true;
			for (int j = 0; j < len; j++) {
				if (str1[(i + j) % len] != str2[j]) {
					flag = false;
					break;
				}

			}
			if (flag) {
				return true;
			}

		}
		return false;
	}

	public static boolean isRotation(String a, String b) {
		if (a == null || b == null || a.length() != b.length()) {
			return false;
		}
		String b2 = b + b;
		return getIndexOf(b2, a) != -1;
	}

	// KMP Algorithm
	public static int getIndexOf(String s, String m) {
		if (s.length() < m.length()) {
			return -1;
		}
		char[] ss = s.toCharArray();
		char[] ms = m.toCharArray();
		int si = 0;
		int mi = 0;
		int[] next = getNextArray(ms);
		while (si < ss.length && mi < ms.length) {
			if (ss[si] == ms[mi]) {
				si++;
				mi++;
			} else if (next[mi] == -1) {
				si++;
			} else {
				mi = next[mi];
			}
		}
		return mi == ms.length ? si - mi : -1;
	}

	public static int[] getNextArray(char[] ms) {
		if (ms.length == 1) {
			return new int[] { -1 };
		}
		int[] next = new int[ms.length];
		next[0] = -1;
		next[1] = 0;
		int pos = 2;
		int cn = 0;
		while (pos < next.length) {
			if (ms[pos - 1] == ms[cn]) {
				next[pos++] = ++cn;
			} else if (cn > 0) {
				cn = next[cn];
			} else {
				next[pos++] = 0;
			}
		}
		return next;
	}

}
